﻿#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
	int pivotIndex(vector<int>& nums) {
		// lsum[i] 表⽰：[0, i - 1] 区间所有元素的和
		// rsum[i] 表⽰：[i + 1, n - 1] 区间所有元素的和
		int n = nums.size();
		vector<int> lsum(n), rsum(n);
		// 预处理前缀和后缀和数组
		for (int i = 1; i < n; i++)
			lsum[i] = lsum[i - 1] + nums[i - 1];
		for (int i = n - 2; i >= 0; i--)
			rsum[i] = rsum[i + 1] + nums[i + 1];
		// 判断
		for (int i = 0; i < n; i++)
			if (lsum[i] == rsum[i])
				return i;
		return -1;
	}
};